/*
 * @lc app=leetcode.cn id=130 lang=golang
 *
 * [130] 被围绕的区域
 */

// @lc code=start
func solve(board [][]byte) {
	m, n := len(board), len(board[0])

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if i != 0 && j != 0 && i != m-1 && j != n-1 {
				continue
			}
			bfs(m, n, i, j, &board)
		}
	}
	// fmt.Println(board)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if board[i][j] == 'O' {
				board[i][j] = 'X'
			}
		}
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if board[i][j] == 'A' {
				board[i][j] = 'O'
			}
		}
	}
	return
}

func bfs(m, n, i, j int, board *[][]byte) {
	if i < 0 || i >= m || j < 0 || j >= n {
		return
	}
	if (*board)[i][j] == 'O' {
		(*board)[i][j] = 'A'
		bfs(m, n, i+1, j, board)
		bfs(m, n, i-1, j, board)
		bfs(m, n, i, j+1, board)
		bfs(m, n, i, j-1, board)
	}
	return
}

// @lc code=end

